// Range v3 library
//
//  Copyright Eric Niebler 2014
//
//  Use, modification and distribution is subject to the
//  Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)
//
// Project home: https://github.com/ericniebler/range-v3
//
//  Copyright 2005 - 2007 Adobe Systems Incorporated
//  Distributed under the MIT License(see accompanying file LICENSE_1_0_0.txt
//  or a copy at http://stlab.adobe.com/licenses.html)

//===----------------------------------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is dual licensed under the MIT and the University of Illinois Open
// Source Licenses. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include <nanorange/algorithm/next_permutation.hpp>
#include <cstring>
#include <utility>
#include <algorithm>
#include "../catch.hpp"
#include "../test_utils.hpp"
#include "../test_iterators.hpp"

namespace ranges = nano::ranges;

namespace {

template <typename T>
constexpr T factorial(T x) {
    T r = 1;
    for (; 1 < x; --x)
        r *=x;
    return r;
}

template <typename Iter, typename Sent = Iter>
void test_iter()
{
	int ia[] = {1, 2, 3, 4, 5, 6};
	const int sa = sizeof(ia) / sizeof(ia[0]);
	int prev[sa];
	for (int e = 0; e <= sa; ++e) {
		int count = 0;
		bool x;
		do {
			std::copy(ia, ia + e, prev);
			x = ranges::next_permutation(Iter(ia), Sent(ia + e)).found;
			if (e > 1) {
				if (x)
					CHECK(std::lexicographical_compare(prev, prev + e, ia,
													   ia + e));
				else
					CHECK(std::lexicographical_compare(ia, ia + e, prev,
													   prev + e));
			}
			++count;
		}
		while (x);
		CHECK(count == factorial(e));
	}
}

template <typename Iter, typename Sent = Iter>
void test_range()
{
	int ia[] = {1, 2, 3, 4, 5, 6};
	const int sa = sizeof(ia) / sizeof(ia[0]);
	int prev[sa];
	for (int e = 0; e <= sa; ++e) {
		int count = 0;
		bool x;
		do {
			std::copy(ia, ia + e, prev);
			x = ranges::next_permutation(
					ranges::subrange(Iter(ia), Sent(ia + e))).found;
			if (e > 1) {
				if (x)
					CHECK(std::lexicographical_compare(prev, prev + e, ia,
													   ia + e));
				else
					CHECK(std::lexicographical_compare(ia, ia + e, prev,
													   prev + e));
			}
			++count;
		}
		while (x);
		CHECK(count == factorial(e));
	}
}

template <typename Iter, typename Sent = Iter>
void test_iter_comp()
{
	typedef std::greater<int> C;
	int ia[] = {6, 5, 4, 3, 2, 1};
	const int sa = sizeof(ia) / sizeof(ia[0]);
	int prev[sa];
	for (int e = 0; e <= sa; ++e) {
		int count = 0;
		bool x;
		do {
			std::copy(ia, ia + e, prev);
			x = ranges::next_permutation(Iter(ia), Sent(ia + e), C()).found;
			if (e > 1) {
				if (x)
					CHECK(std::lexicographical_compare(prev, prev + e, ia,
													   ia + e, C()));
				else
					CHECK(std::lexicographical_compare(ia, ia + e, prev,
													   prev + e, C()));
			}
			++count;
		}
		while (x);
		CHECK(count == factorial(e));
	}
}

template <typename Iter, typename Sent = Iter>
void test_range_comp()
{
	typedef std::greater<int> C;
	int ia[] = {6, 5, 4, 3, 2, 1};
	const int sa = sizeof(ia) / sizeof(ia[0]);
	int prev[sa];
	for (int e = 0; e <= sa; ++e) {
		int count = 0;
		bool x;
		do {
			std::copy(ia, ia + e, prev);
			x = ranges::next_permutation(
					ranges::subrange(Iter(ia), Sent(ia + e)), C()).found;
			if (e > 1) {
				if (x)
					CHECK(std::lexicographical_compare(prev, prev + e, ia,
													   ia + e, C()));
				else
					CHECK(std::lexicographical_compare(ia, ia + e, prev,
													   prev + e, C()));
			}
			++count;
		}
		while (x);
		CHECK(count == factorial(e));
	}
}

struct c_str {
	char const* value;

	friend bool operator==(c_str a, c_str b)
	{
		return 0 == std::strcmp(a.value, b.value);
	}

	friend bool operator!=(c_str a, c_str b)
	{
		return !(a == b);
	}
};

// For debugging the projection test
std::ostream& operator<<(std::ostream& sout, std::pair<int, c_str> p)
{
	return sout << "{" << p.first << "," << p.second.value << "}";
}

}

TEST_CASE("alg.next_permutation")
{
	test_iter<bidirectional_iterator<int*> >();
	test_iter<random_access_iterator<int*> >();
	test_iter<int*>();

	test_iter<bidirectional_iterator<int*>, sentinel<int*> >();
	test_iter<random_access_iterator<int*>, sentinel<int*> >();

	test_iter_comp<bidirectional_iterator<int*> >();
	test_iter_comp<random_access_iterator<int*> >();
	test_iter_comp<int*>();

	test_iter_comp<bidirectional_iterator<int*>, sentinel<int*> >();
	test_iter_comp<random_access_iterator<int*>, sentinel<int*> >();

	test_range<bidirectional_iterator<int*> >();
	test_range<random_access_iterator<int*> >();
	test_range<int*>();

	test_range<bidirectional_iterator<int*>, sentinel<int*> >();
	test_range<random_access_iterator<int*>, sentinel<int*> >();

	test_range_comp<bidirectional_iterator<int*> >();
	test_range_comp<random_access_iterator<int*> >();
	test_range_comp<int*>();

	test_range_comp<bidirectional_iterator<int*>, sentinel<int*> >();
	test_range_comp<random_access_iterator<int*>, sentinel<int*> >();

	// Test projection

	typedef std::greater<int> C;
	std::pair<int, c_str> ia[] = {{6, {"six"}}, {5,{"five"}}, {4,{"four"}}, {3,{"three"}}, {2,{"two"}}, {1,{"one"}}};
	CHECK(ranges::next_permutation(ia, C(), &std::pair<int,c_str>::first).found);
	::check_equal<std::pair<int, c_str>>(ia, {{6, {"six"}}, {5,{"five"}}, {4,{"four"}}, {3,{"three"}}, {1,{"one"}}, {2,{"two"}}});
	CHECK(ranges::next_permutation(ia, C(), &std::pair<int,c_str>::first).found);
	::check_equal<std::pair<int, c_str>>(ia, {{6, {"six"}}, {5,{"five"}}, {4,{"four"}}, {2,{"two"}}, {3,{"three"}}, {1,{"one"}}});
	CHECK(ranges::next_permutation(ia, C(), &std::pair<int,c_str>::first).found);
	::check_equal<std::pair<int, c_str>>(ia, {{6, {"six"}}, {5,{"five"}}, {4,{"four"}}, {2,{"two"}}, {1,{"one"}}, {3,{"three"}}});
	// etc..
}
